

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

class Solution
{
    using PII = pair<int, int>;
public:
    int eatenApples(vector<int>& apples, vector<int>& days)
    {
        int res = 0;
        //priority_queue<PII, deque<PII>, greater<PII>> minheap;
        //priority_queue<PII, deque<PII>, Greater> minheap;
        priority_queue<PII, vector<PII>, greater<PII>> minheap;

        for (int i = 0, n = apples.size(); i < n || minheap.size(); ++i)
        {
            while (minheap.size() && i > minheap.top().first)
            {
                minheap.pop();
            }

            if (i < n && apples[i])
            {
                minheap.push({ i + days[i] - 1, apples[i] });
            }

            if (minheap.size())
            {
                auto top = minheap.top();
                minheap.pop();

                if (--top.second > 0)
                    minheap.push(top);
                ++res;
            }
        }

        return res;
    }

    string replaceWords(vector<string>& dictionary, string sentence)
    {
        string res;
        int n = sentence.size();
        unordered_set<string> hash(dictionary.begin(), dictionary.end());

        for (int beg = 0, end = 0; beg < n;)
        {
            res += ' ';
            for (end = beg; end < n && !isblank(sentence[end]); ++end)
            {
                string tmp = sentence.substr(beg, end - beg + 1);
                if (hash.count(tmp))
                {
                    ++end;
                    break;
                }
            }
            res += sentence.substr(beg, end - beg);

            while (end < n && !isblank(sentence[end]))
            {
                ++end;
            }
            beg = end + 1;
        }

        return res.substr(1);
    }

private:
    struct Greater
    {
        bool operator()(const PII& x, const PII& y)
        {
            return x > y;
        }
    };
};

int main()
{
	return 0;
}